In personal video teleconferencing, telephone channels of relatively narrow bandwidth are commonly used to transmit video images. Under one standard, ISDN-BR1, the bandwidth is typically 128 Kilo-bits per second. Because full-motion, or near full-motion, video images generally require a larger bandwidth, data compression is used to fit the video data into the limited-bandwidth ISDN channel. However, the channel is not a perfect transmission line: a small probability exists that some data will be lost during transmission, because of (a) various errors occurring within the channel, and (b) traffic congestion over packet-switched networks.
In explaining selected aspects of these errors, this Background will (a) first discuss the frame structure for one type of standard digital image, (b) illustrate a digital image, conforming to the frame structure, and which contains regions of lost data, and then (c) discuss several prior-art approaches used to correct the lost data.
FIG. 1 illustrates the frame structure for an image transmitted using the H.261 format, which is a format established by the International Telecommunications Union, Telecommunications division, or ITU-T. The frame 3, which represents the video image seen by a viewer, takes the form of a pixel matrix of 288 lines, each containing 352 pixels, as indicated. The frame is divided into 12 Groups of Blocks, GOBs. Each GOB is divided into 33 Macro Blocks, MB. Each MB consists of an 16.times.16 array of pixels, as indicated.
FIG. 2 illustrates a representative picture to be transmitted. FIG. 3 illustrates the same picture, but with seven MBs removed, for experimental purposes. The missing MBs are labeled "MB." That Figure contains 12 GOBs, consistent with FIG. 1. Several prior-art approaches to correcting the missing MBs will now be discussed.
Automatic Repeat Request (ARO). A simple correction procedure detects the fact that MBs are missing, and requests a re-transmission of the missing MBs. However, this approach can impose significant delay in certain situations, and may create greater traffic congestion over the network.
Replacement by MB of Previous Frame. Another simple correction procedure replaces each missing MB with the MB which occupied the same position, but in the previous frame. In effect, the previous MB, in the previous frame, is "held over."
However, this approach requires a storage buffer to hold the previous MBs, in anticipation of the contingency that they will be needed as replacements for the subsequent frame. Also, if the image contains motion, as when the image shows a person walking, then this approach can produce jerky motion, as well as flash-like artifacts where the replacement occurs.
Replacement by Adjacent MB in Same Frame (RAB). The missing MB can be replaced by an adjacent MB in the same frame. In this approach, the adjacent MB now appears twice in the image: once at its original location, and once at location of the missing MB.
FIG. 4 illustrates this approach, applied to the picture of FIG. 3. Attention will be focused on the missing MB in GOB 5 in FIG. 3. (It is not practical to apply labels to FIG. 4.) This missing MB, located to the woman's right of her nose, has been replaced by the adjacent MB, as indicated in FIG. 4. The replacement MB contains part of her right eye, and appears twice: once in the normal position, and once to the woman's right of her nose.
The other missing MBs in FIG. 3 are replaced in a similar way, as FIG. 4 indicates. Every missing MB is replaced by an MB located horizontally adjacent.
FIG. 4 indicates that the results of this approach are not perfect. Further, it has been found that, if the replacement MB has a high contrast with the surrounding area, visual flashes can occur, as in the previous replacement approach.
Replacement by Interpolation of Neighboring Blocks. Each pixel in an MB is approximated by a linear, or polynomial, interpolation with the pixels of the surrounding blocks.
In FIG. 5A, block M is missing. It is surrounded by a north block, B.sub.n, a northwest block, B.sub.nw, a west block, B.sub.w, and so on. For every pixel in the missing block M, a replacement is computed, according to the following function: EQU M=w.sub.nw B.sub.nw +w.sub.n B.sub.n +w.sub.ne B.sub.ne +w.sub.e B.sub.e +w.sub.se B.sub.se +w.sub.s B.sub.s +w.sub.sw B.sub.sw +w.sub.w B.sub.w(1)
wherein
each "w" represents a weighting factor, and PA1 each "B" and the "M" represent matrices. PA1 the P's represent pixel values of the single-pixel-wide boundary located outside the missing block M, as indicated in FIG. 7, and labeled P.sub.n, P.sub.e, etc.; PA1 the R's represent missing pixel values, in the single-pixel-wide boundary located at the inside edge of the missing block M, as indicated in FIG. 7, and labeled R.sub.n, R.sub.e, etc.; and PA1 the symbol t represents the transpose of a vector matrix. PA1 wherein EQU t=(x-x.sub.1)/(x.sub.3 -x.sub.1) and EQU u=(y-y.sub.1)/(y.sub.3 -y.sub.1).
FIG. 5C provides an example of the computation, using a 5.times.5 pixel matrix in each block for simplicity. As indicated, for each pixel within matrix M, the corresponding pixel within each block "B" is multiplied by its weighting factor "w", and the sum of these products produces the pixel value in M, as the equation in FIG. 5C indicates.
In a variant of this approach, fewer than eight neighboring blocks are used. For example, only the north, south, east, and west "B's" can be used, and FIG. 5B provides an example.
Replacement by Averaging Four Nearest Neighbors (Unconstrained Least Squares, ULS). This may be viewed as another variant of the previous approach. The weights in function (1) are all identical, at 0.25. Only the north, south, east, and west MBs are used. The function used is the following: EQU M=(B.sub.n +B.sub.w +B.sub.e +B.sub.s)/4 (2)
Again, this is a matrix equation.
FIG. 6 provides an example of synthesis of missing MBs, using this approach. Again, it can be seen that the results are not perfect.
Replacement by Weighted Sum of Nearest Neighbors (Constrained Least Squares, CLS). This approach utilizes the following function: EQU M=w.sub.n B.sub.n +w.sub.w B.sub.w +w.sub.e B.sub.e +w.sub.s B.sub.s(3)
wherein the "B's" again are matrices, containing the pixel values of the surrounding MBs, as in FIG. 5.
Function (3), although similar in form to function (2), is different in implementation: the weights, w, in function (3) are not predetermined constants, but are computed, based on surrounding pixels. In this computation, squared error vectors, E, are obtained, as follows: EQU E.sup.2.sub.n =(P.sub.n -R.sub.n).sup.t (P.sub.n -R.sub.n) EQU E.sup.2.sub.s =(P.sub.s -R.sub.s).sup.t (P.sub.s -R.sub.s) EQU E.sup.2.sub.w =(P.sub.w -R.sub.w).sup.t (P.sub.w -R.sub.w) EQU E.sup.2.sub.e =(P.sub.e -R.sub.e).sup.t (P.sub.e -R.sub.e)
wherein
In effect, each error-term E within each vector represents a square of the difference between (a) a pixel at the inside edge of M (ie, within a row or a column R in FIG. 7), and (b) a bordering pixel (ie, within a row or column P in FIG. 7).
The system of equations is solved by minimizing the "E" variables, thereby producing the "P" variables, as by using known estimation techniques, which produce closed-form solutions. In the solution, the weights are computed based the solution to the following optimization function: EQU min E.sup.2 =w.sub.n E.sup.2.sub.n +w.sub.w E.sup.2.sub.s +w.sub.e E.sup.2.sub.w +w.sub.s E.sup.2.sub.e
Once the outermost border of single pixels of the missing MB is computed, using function (3), the next-innermost border is computed, and so on. In a sense, the pixels at the edges of concentric squares are computed, beginning with the largest square.
FIG. 8 provides an example of synthesis of missing MBs, using this approach.
Replacement by First-Order Polynomial Interpolation (Bilinear Interpolation, BI). This approach uses the values of pixels at the four corners bounding the missing MP, which are indicated in FIG. 9. (Using pixels at the corners is exemplary; other pixels along the boundary can be used.) The estimated value of a missing pixel, g(x, y), is given by the following function: EQU g(x, y)=(1-t)ug.sub.nw +tug.sub.ne +t(1-u)g.sub.sw +(1-t) (1-u)g.sub.se.(4)
In another implementation, the four corner-pixels in FIG. 9 can be replaced by clusters of pixels.
In general, this approach may be viewed as finding a two-dimensional mean of a variable, g. FIG. 10 provides an example of synthesis of missing MBs, using this approach.
Replacement by Multi-Directional Non-Linear Interpolation. This approach is discussed in "Multidirectional Interpolation for Spatial Error Concealment," by W. Kwok and H. Sun, in IEEE Transactions on Consumer Electronics, vol. 39, no. 3, pp. 455-460 (August, 1993). A simplified summary is given as follows.
FIG. 11 illustrates a missing block M and four surrounding blocks B.sub.n, B.sub.e, B.sub.s, and B.sub.w. For each pixel within the surrounding blocks, a gradient, and magnitude, are obtained. The insert, indicated by arrow 30, shows five pixels in enlarged form, centered about the pixel which is labeled "80" in the insert, which indicates the pixel value.
Magnitudes of surrounding pixels are also given in the insert 30. The gradient is, in effect, the direction in which the maximum slope occurs. Slope is the change in pixel value with respect to distance. In FIG. 11, the highest slope occurs between the "80" pixel and the "5" pixel. The magnitude of the slope is 75, and the direction is downward, as indicated by the arrow labeled "75" and pointing downward. Gradients for multiple pixels are obtained, some of which are indicated by the arrows in FIG. 12.
The approach searches out gradients which lie on a common line, such as dashed line 33. Of these lines, the approach seeks lines which pass through the missing block M. When such lines are found, an interpolation is performed along the line, between extremum points.
For example, in FIG. 12, pixels P2 through P7 would be interpolated, based on the values of P1 and P8.
This approach produces poor results when the missing block M lies within a textured region. Also, the approach is noise-sensitive, and can generate false edges within the missing block M. Further, this approach requires extensive computation time.
The invention provides an approach for synthesis of missing blocks of data which eliminates many of the disadvantages inherent in the approaches just discussed.